home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The Original Shareware 1.1
/
The Original Shareware (WeMake CDs)(Volume 1.1)(CDs, Inc)(1993).iso
/
19
/
madtrb40.zip
/
MSTREES.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1986-05-04
|
43KB
|
1,040 lines
{ *************************************************************************** }
{ * * }
{ * MEDIAN SPLIT TREE PROGRAM * }
{ * * }
{ * Class: CS 577 * }
{ * Instructor: Manber * }
{ * * }
{ * Written by Chris Maeder * }
{ * Edited and Compiled using Turbo Pascal * }
{ * on an IBM PC * }
{ * * }
{ *************************************************************************** }
Const
MAX_KEYS_PER_NODE=3; { maximum number of look-up keys for any given tree node,
not including split key }
MAX_KEY_SIZE=15; { maximum size of string used to store a key }
Type
KeyString=String[MAX_KEY_SIZE]; { a string type used to store look-up keys }
FrequencyType=0..MAXINT; { allowable integer values that a key's frquency value can take on }
NodeKeyElement= { a look-up key node element type }
Record
Key:KeyString; { look-up key string }
Frequency:FrequencyType; { frequency value }
End; { NodeKeyElement record }
KeyArray= { an array of look-up keys }
Array[1..MAX_KEYS_PER_NODE] of NodeKeyElement;
TreeNodePtr=^TreeNodeType; { a pointer which points to the tree node type 'TreeNodeType' }
TreeNodeType= { a n-MST node of }
Record
NodeKeys:KeyArray; { an array of look-up keys }
SplitKey:NodeKeyElement; { a key that splits the left and right subtree keys }
Left:TreeNodePtr; { a pointer to tree node's left son }
Right:TreeNodePtr; { a pointer to tree node's right son }
End; { TreeNodeType record }
L_L_ElementPtr=^L_L_ElementType; { a pointer to the doubly linked list element type 'L_L_ElementType' }
L_L_ElementType= { a doubly linked list element }
Record
Key:KeyString; { look-up key }
Frequency:FrequencyType; { frequency value }
Front:L_L_ElementPtr; { a pointer to the forward element }
Back:L_L_ElementPtr; { a pointer to the rearward element }
End; { L_L_ElementType record }
Var
L_L_HeadPtr:L_L_ElementPtr; { a pointer to the head of the doubly linked list }
L_L_TailPtr:L_L_ElementPtr; { a pointer to the tail of the doubly linked list }
MST_RootPtr:TreeNodePtr; { a pointer to the root node of the MST }
HoldPtr:Integer; { a pointer used to temporarily store console screen output vector }
Procedure InitProgram;
{ This procedure initializes all the global variables and pointers used in this
program. }
Begin { InitProgram }
L_L_HeadPtr:=Nil;
L_L_TailPtr:=Nil;
HoldPtr:=ConOutPtr;
End; { InitProgram }
Procedure HardCopy( On:Boolean);
{ This procedure reroutes the output from the screen to the printer. }
Begin { HardCopy }
If On Then
Begin
HoldPtr:=ConOutPtr;
ConOutPtr:=LstOutPtr;
End { If On }
Else
Begin
ConOutPtr:=HoldPtr;
End; { Else }
End; { HardCopy }
Procedure ReadInputFileModule;
{ *************************************************************************** }
{ * * }
{ * READ INPUT FILE MODULE * }
{ * * }
{ * This module reads the file entries out of the declared input * }
{ * file. Each file entry contains a look-up key and a value * }
{ * corresponding to its frequency count. * }
{ * * }
{ * The file entries are assumed to already be in sorted order * }
{ * according to the look-up keys lexical value. These entries are * }
{ * then placed in a doubly linked list, maintaining their sorted * }
{ * lexical order. * }
{ * * }
{ *************************************************************************** }
Const
MAX_FILE_ENTRY_SIZE=50; { maximum size of the file entry string }
FILE_NAME='KeyData1.Dat'; { name of the input data file }
Type
FileEntryString=String[MAX_FILE_ENTRY_SIZE]; { a string type used to store file entries }
Var
DataFile:Text; { text file }
FileEntry:FileEntryString; { variable used in reading entries out of input data file }
Procedure RemoveFirstEntryFromString(Var Text:FileEntryString);
{ This procedure removes the first text entry from the passed text string and
returns the new truncated text string. The text entries in the passed text
string are assumed to be delinated by one space. See the following
example.
Passed: Entry1 Entry2 Entry3
Returned: Entry2 Entry3 }
Begin { RemoveFirstEntryFromString }
If Pos(' ',Text)<>0 Then
Text:=Copy(Text,(Pos(' ',Text)+1),(Length(Text)-Pos(' ',Text)));
End; { RemoveFirstEntryFromString }
Procedure ReturnFirstEntryFromString(Var Text:FileEntryString);
{ This procedure removes the first text entry from the passed text string and
returns the first text entry. The text entries in the passed text string
are assumed to be delinated by one space. See the following example.
Passed: Entry1 Entry2 Entry3
Returned: Entry1 }
Begin { ReturnFirstEntryFromString }
If Pos(' ',Text)<>0 Then
Text:=Copy(Text,1,(Pos(' ',Text)-1));
End; { ReturnFirstEntryFromString }
Function DetermineKeyFromFileEntry( Entry:FileEntryString):KeyString;
{ This function is passed a file entry which contains a look-up key as the
first entry. This function picks off the look-up key from the file entry
and passes the look-up key back. }
Begin { DetermineKeyFromFileEntry }
ReturnFirstEntryFromString(Entry);
DetermineKeyFromFileEntry:=Entry;
End; { DetermineKeyFromFileEntry }
Function DetermineFrequencyFromFileEntry( Entry:FileEntryString):FrequencyType;
{ This function is passed a file entry which contains a frequency count for a
look-up key as the second entry. This function picks off the frequency
count from the file entry and passes the frequency count back. }
Var
Frequency:Integer; { a temporary variable used in conversion of string to real }
ErrorCode:Integer; { a variable used in checking for error in conversion }
Begin { DetermineFrquencyFromFileEntry }
RemoveFirstEntryFromString(Entry);
ReturnFirstEntryFromString(Entry);
Val(Entry,Frequency,ErrorCode);
DetermineFrequencyFromFileEntry:=Frequency;
End; { DetermineFrquencyFromFileEntry }
Procedure AddKeyToLinkedList(Var HeadPtr,
TailPtr: L_L_ElementPtr;
FileEntry:FileEntryString);
{ This procedure places the passed file entry onto the end of the doubly
linked list. By adding the passed file entry to the end of the doubly
linked list maintains the assumed lexical ordering of the keys. }
Var
New_L_L_Element:L_L_ElementPtr; { a pointer to a new doubly linked list element which will be added to the tail
of the passed linked list }
Begin { AddKeyToLinkedList }
New(New_L_L_Element); { create a new queue element to add to the end of the passed linked list }
With New_L_L_Element^ Do
Begin { routine to enter information into new linked list element }
Key:=DetermineKeyFromFileEntry(FileEntry);
Frequency:=DetermineFrequencyFromFileEntry(FileEntry);
Front:=Nil; { set forward pointer to Nil }
Back:=Nil; { set backward pointer to Nil }
End; { With New_L_L_Element }
If HeadPtr=Nil Then
Begin { Special Case One - linked list not yet in existance }
HeadPtr:=New_L_L_Element; { set passed linked list head pointer to point to first element in the linked list }
TailPtr:=New_L_L_Element; { set passed linked list tail pointer to point to first element in the linked list }
End { If HeadPtr }
Else
Begin { Special Case Two - linked list in existance }
TailPtr^.Back:=New_L_L_Element; { link new element to end of linked list }
New_L_L_Element^.Front:=TailPtr; { link new element to end of linked list }
TailPtr:=New_L_L_Element; { increment tail pointer }
End; { Else }
End; { AddKeyToLinkedList }
Begin { ReadInputFileModule }
Assign(DataFile,FILE_NAME); { assign to a disk file }
Reset(DataFile); { open the file for reading }
Repeat { read in the file entries }
ReadLn(DataFile,FileEntry);
AddKeyToLinkedList(L_L_HeadPtr,L_L_TailPtr,FileEntry);
Until Eof(DataFile); { read until end of file found }
Close(DataFile); { close the disk file }
End; { ReadInputFileModule }
Procedure PrintLinkedList( L_L_HeadPtr,
L_L_TailPtr:L_L_ElementPtr);
{ This procedure prints out the the doubly linked list containing the look-up
keys. }
Var
L_L_NodePtr:L_L_ElementPtr; { a pointer used to traverse the doubly linked list }
Begin { PrintLinkedList }
WriteLn;
WriteLn;
WriteLn('LINKED LIST OF LOOK-UP KEYS AND');
WriteLn('CORRESPONDING FREQUENCIES FOLLOWS:');
WriteLn('----------------------------------');
WriteLn;
WriteLn;
If L_L_HeadPtr<>Nil Then
Begin
L_L_NodePtr:=L_L_HeadPtr;
WriteLn(L_L_NodePtr^.Key,' ',L_L_NodePtr^.Frequency);
While L_L_NodePtr<>L_L_TailPtr Do
Begin
L_L_NodePtr:=L_L_NodePtr^.Back;
WriteLn(L_L_NodePtr^.Key,' ',L_L_NodePtr^.Frequency);
End; { While L_L_NodePtr }
End { If L_L_HeadPtr }
Else
WriteLn('No elements in linked list');
End; { PrintLinkedList }
Procedure Build_MST_Module;
{ *************************************************************************** }
{ * * }
{ * BUILD MEDIAN SPLIT TREE MODULE * }
{ * * }
{ * This module controls the building of the n-MST (median split * }
{ * tree). There are n entries per node where the n-1 most frequently * }
{ * accessed keys in the subtree and the median of the rest of the * }
{ * keys in the subtree. * }
{ * * }
{ * Observe that n=1 produces a balanced binary search tree, n=2 * }
{ * produces a conventional median split tree, and n=total number of * }
{ * look-up keys produces a sequential search. * }
{ * * }
{ *************************************************************************** }
Type
ChildType=(LEFT,RIGHT,ROOT); { an enumerated data type used to determine how to link child
node with parent node }
Procedure SortKeyArray(Var SetOfKeys:KeyArray);
{ This procedure controls the quicksort on the passed array of look-up keys
so that they are sorted in ascending order according to their lexical ( or
alphabetical) order. }
Procedure QuickSort( LowElement,
HighElement:Integer;
Var SetOfKeys: KeyArray);
{ This is a recursive procedure that sorts the passed array of look-up keys
by first determining a pivotal element and then partitions the remaining
elements (between LowElement and HighElement of the passed SetOfKeys)
according to that pivotal element. }
Var
LowIndex:Integer; { an incremented index starting at the low element in the passed set of keys }
HighIndex:Integer; { an incremented index starting at the high element in the passed set of keys }
PivotalKey:KeyString; { a look-up key which acts as a pivotal element }
TemporaryNodeElement:NodeKeyElement; { a node key element used in transposing elements in the set of keys }
Begin { QuickSort }
LowIndex:=LowElement;
HighIndex:=HighElement;
PivotalKey:=SetOfKeys[(LowElement+HighElement) Div 2].Key;
Repeat
While SetOfKeys[LowIndex].Key<PivotalKey Do
LowIndex:=LowIndex+1;
While PivotalKey<SetOfKeys[HighIndex].Key Do
HighIndex:=HighIndex-1;
If LowIndex<=HighIndex Then
Begin { transpose elements in key array }
TemporaryNodeElement:=SetOfKeys[LowIndex];
SetOfKeys[LowIndex]:=SetOfKeys[HighIndex];
SetOfKeys[HighIndex]:=TemporaryNodeElement;
LowIndex:=LowIndex+1;
HighIndex:=HighIndex-1;
End; { If LowIndex }
Until LowIndex>HighIndex;
If LowElement<HighIndex Then
QuickSort(LowElement,
HighIndex,
SetOfKeys);
If LowElement<HighElement Then
QuickSort(LowIndex,
HighElement,
SetOfKeys);
End; { QuickSort }
Begin { SortKeyArray }
QuickSort(1,
MAX_KEYS_PER_NODE,
SetOfKeys);
End; { SortKeyArray }
Function EmptyLinkedList( L_L_HeadPtr:L_L_ElementPtr):Boolean;
{ This function is used to check if the passed linked list is empty. If the
linked list is empty, this function returns as true, else it returns as
false. }
Begin { EmptyLinkedList }
If L_L_HeadPtr=Nil Then
EmptyLinkedList:=True
Else
EmptyLinkedList:=False;
End; { EmptyLinkedList }
Function SplitValue( NumberOf_L_L_Elements:Integer):Integer;
{ This function determines the index to the key that should be used as the
split key value for the passed number of elements remaining in the doubly
linked list.
Observe that instead of selecting the median as the split value, a more
balanced MST can be formed by selecting the key whose index in the lexical
order is maximized where the split value is given by
SplitValue=((MAX_KEYS_PER_NODE+1)*IntegerMultiplier)+1
closest to median value for the passed number of linked list elements.
This algorithm produces an unbalanced, but complete tree in which all but
at most one node are completely filled with look-up keys including split
keys, in which the overflow tends toward the left most son. }
Var
IntegerMultiplier:Integer; { an incremented integer used as an exponent }
MedianValue:Integer; { an integer variable used to temporaily store the median value }
PossibleSplitValue:Integer; { an integer variable used in determining the split value }
Begin { SplitValue }
IntegerMultiplier:=1; { initialized incremented integer }
MedianValue:=(NumberOf_L_L_Elements Div 2);
PossibleSplitValue:=1; { initialize split value }
While (Abs((IntegerMultiplier*(MAX_KEYS_PER_NODE+1))+1)-MedianValue<=
Abs(PossibleSplitValue-MedianValue)) Do
Begin
PossibleSplitValue:=(IntegerMultiplier*(MAX_KEYS_PER_NODE+1))+1;
IntegerMultiplier:=IntegerMultiplier+1;
End; { While Abs }
SplitValue:=PossibleSplitValue;
End; { SplitValue }
Procedure DetermineSplitKey(Var L_L_HeadPtr,
L_L_TailPtr,
L_L_SplitKey,
Left_L_L_HeadPtr,
Left_L_L_TailPtr,
Right_L_L_HeadPtr,
Right_L_L_TailPtr:L_L_ElementPtr);
{ This procedure from the linked list returns the median split key element
and the newly split linked list (at the split key element) to the calling
routine. }
Var
Count:Integer; { a variable used to determine number of elements in the passed linked list }
L_L_Element:L_L_ElementPtr; { a pointer used in traversing the passed linked list }
L_L_Index:Integer; { a variable used to traverse the linked list }
Begin { DetermineSplitKey }
If Not EmptyLinkedList(L_L_HeadPtr) Then
Begin
{ determine number of elements in passed linked list }
Count:=1; { initialize counter }
L_L_Element:=L_L_HeadPtr; { initialize traversal element }
While L_L_Element<>L_L_TailPtr Do
Begin
Count:=Count+1; { increment counter }
L_L_Element:=L_L_Element^.Back; { increment pointer }
End; { While L_L_Element }
{ locate split key element }
L_L_Element:=L_L_HeadPtr; { initialize traversal element }
For L_L_Index:=2 To SplitValue(Count) Do
L_L_Element:=L_L_Element^.Back;
{ split key has been found }
L_L_SplitKey:=L_L_Element;
{ now split current linked list about split key }
{ split left half of linked list }
If L_L_SplitKey<>L_L_HeadPtr Then
Begin
Left_L_L_HeadPtr:=L_L_HeadPtr;
Left_L_L_TailPtr:=L_L_SplitKey^.Front;
Left_L_L_TailPtr^.Back:=Nil;
End { If L_L_SplitKey }
Else
Begin
Left_L_L_HeadPtr:=Nil;
Left_L_L_TailPtr:=Nil;
End; { Else }
{ split right half of linked list }
If L_L_SplitKey<>L_L_TailPtr Then
Begin
Right_L_L_HeadPtr:=L_L_SplitKey^.Back;
Right_L_L_HeadPtr^.Front:=Nil;
Right_L_L_TailPtr:=L_L_TailPtr;
End { If L_L_SplitKey }
Else
Begin
Right_L_L_HeadPtr:=Nil;
Right_L_L_TailPtr:=Nil;
End { Else }
End { If Not EmptyLinkedList }
Else
Begin
Left_L_L_HeadPtr:=Nil;
Left_L_L_TailPtr:=Nil;
Right_L_L_HeadPtr:=Nil;
Right_L_L_TailPtr:=Nil;
L_L_SplitKey^.Key:='';
L_L_SplitKey^.Frequency:=0;
End; { Else }
L_L_SplitKey^.Front:=Nil; { disconnect link }
L_L_SplitKey^.Back:=Nil; { disconnect link }
End; { DetermineSplitKey }
Procedure RemoveElementFromLinkedList(Var L_L_HeadPtr,
L_L_TailPtr,
RemoveElement:L_L_ElementPtr);
{ This procedure removes the passed element from the passed doubly linked
list.
Example Linked List:
______
__ __ | __ | __ __ __
Nil<---|__|<--->|__|<-- |__| -->|__|<--->|__|<--->|__|--->Nil
HeadPtr--^ ^--RemoveElement ^--TailPtr
Note that there are four special cases when deleting an element from the
passed linked list:
1. Delete last remaining element from linked list.
2. Delete element from front of linked list.
3. Delete element from end of linked list.
4. Delete element from middle of linked list. }
Begin { RemoveElementFromLinkedList }
{ Special Case One - Check if deleting last remaining element from linked list }
If L_L_HeadPtr=L_L_TailPtr Then
Begin { delete last remaining element from linked list }
L_L_HeadPtr:=Nil;
L_L_TailPtr:=Nil;
End { If L_L_HeadPtr }
Else
{ Special Case Two - Check if deleting element from front of linked list }
If L_L_HeadPtr=RemoveElement Then
Begin { delete element from front of linked list }
RemoveElement^.Back^.Front:=Nil; { release link with list }
L_L_HeadPtr:=RemoveElement^.Back; { increment head pointer }
End { If L_L_HeadPtr }
Else
{ Special Case Three - Check if deleting element from rear of linked list }
If L_L_TailPtr=RemoveElement Then
Begin { delete element from end of linked list }
RemoveElement^.Front^.Back:=Nil; { release link with list }
L_L_TailPtr:=RemoveElement^.Front; { decrement tail pointer }
End { If L_L_TailPtr }
Else
{ Special Case Four - Deleting element from middle of linked list }
Begin
RemoveElement^.Front^.Back:=RemoveElement^.Back; { re-link list }
RemoveElement^.Back^.Front:=RemoveElement^.Front; { re-link list }
End; { Else }
End; { RemoveElementFromLinkedList }
Procedure DetermineMostFrequentKey(Var L_L_HeadPtr,
L_L_TailPtr,
FrequentKey:L_L_ElementPtr);
{ This procedure determines the most frequent occurring look-up key in the
passed linked list of look-up keys, using their corresponding frequency
values.
This procedure then returns this most frequently occurring key to the
calling routine, while also removing the key from the passed linked list.
Observe that this procedure uses a sequential search to find the most
frequently occurring key. This algorithm is slow and clearly could be
improved by keeping the keys sorted both in lexical and frequency order.
Since the median split tree is normally only built once and then used, it
was decided to keep this implementation simple. }
Var
L_L_Element:L_L_ElementPtr; { a pointer used in traversing the passed linked list }
Begin { DetermineMostFrequentKey }
If Not EmptyLinkedList(L_L_HeadPtr) Then
Begin { determine most frequent key in linked list }
FrequentKey:=L_L_HeadPtr; { initialize the most frequent key pointer }
L_L_Element:=L_L_HeadPtr; { initialize linked list traversing pointer }
While L_L_Element<>L_L_TailPtr Do
Begin
L_L_Element:=L_L_Element^.Back; { increment the traversing pointer }
If L_L_Element^.Frequency>FrequentKey^.Frequency Then
FrequentKey:=L_L_Element;
End; { While L_L_Element }
RemoveElementFromLinkedList(L_L_HeadPtr,
L_L_TailPtr,
FrequentKey);
FrequentKey^.Front:=Nil;
FrequentKey^.Back:=Nil;
End { If Not EmptyLinkedList }
Else
With FrequentKey^ Do
Begin { linked list is empty, hence return an empty entry }
Key:='';
Frequency:=0;
Front:=Nil;
Back:=Nil;
End; { With FrequentKey }
End; { DetermineMostFrequentKey }
Procedure Fill_MST_Node(Var L_L_HeadPtr,
L_L_TailPtr: L_L_ElementPtr;
Var TreeNode: TreeNodePtr;
Var Left_L_L_HeadPtr,
Left_L_L_TailPtr,
Right_L_L_HeadPtr,
Right_L_L_TailPtr:L_L_ElementPtr);
{ This procedure takes the passed linked list of look-up keys, takes the n
most frequently occurring keys from the linked list, places them into the
passed key array, sorts the keys according to their lexical order,
determines the split key and then splits the linked list accordingly, and
finally returns the passed tree node and the split linked list back to the
calling routine. }
Var
ArrayIndex:Integer; { an index counter used in filling the look-up key array }
L_L_Element:L_L_ElementPtr; { a pointer to a removed linked list element }
Begin { Fill_MST_Node }
{ fill the node's key array }
For ArrayIndex:=1 To MAX_KEYS_PER_NODE Do
Begin
DetermineMostFrequentKey(L_L_HeadPtr,
L_L_TailPtr,
L_L_Element);
With TreeNode^ Do
Begin
NodeKeys[ArrayIndex].Key:=L_L_Element^.Key;
NodeKeys[ArrayIndex].Frequency:=L_L_Element^.Frequency;
End; { With TreeNode }
End; { For ArrayElement }
SortKeyArray(TreeNode^.NodeKeys); { sort the keys according to their lexical order }
{ determine split key and split linked list }
DetermineSplitKey(L_L_HeadPtr,
L_L_TailPtr,
L_L_Element,
Left_L_L_HeadPtr,
Left_L_L_TailPtr,
Right_L_L_HeadPtr,
Right_L_L_TailPtr);
With TreeNode^ Do
Begin
SplitKey.Key:=L_L_Element^.Key;
SplitKey.Frequency:=L_L_Element^.Frequency;
Left:=Nil; { set left child ptr to Nil }
Right:=Nil; { set right child ptr to Nil }
End; { With TreeNode^ }
End; { Fill_MST_Node }
Procedure Build_MST_Node(Var L_L_HeadPtr,
L_L_TailPtr: L_L_ElementPtr;
Var ParentTreeNode:TreeNodePtr;
ParentBranch: ChildType);
{ This recursive procedure does the actual building of the n degree median
split tree. }
Var
CurrentTreeNode:TreeNodePtr; { a MST node pointer used in adding new nodes to the MST }
Left_L_L_HeadPtr:L_L_ElementPtr; { pointer to the newly split linked list of look-up keys }
Left_L_L_TailPtr:L_L_ElementPtr; { pointer to the newly split linked list of look-up keys }
Right_L_L_HeadPtr:L_L_ElementPtr; { pointer to the newly split linked list of look-up keys }
Right_L_L_TailPtr:L_L_ElementPtr; { pointer to the newly split linked list of look-up keys }
Begin { Build_MST_Node }
If Not EmptyLinkedList(L_L_HeadPtr) Then
Begin
{ build current node }
New(CurrentTreeNode); { allocate an MST node }
Fill_MST_Node(L_L_HeadPtr, { fill the MST node with keys from the linked list }
L_L_TailPtr,
CurrentTreeNode,
Left_L_L_HeadPtr,
Left_L_L_TailPtr,
Right_L_L_HeadPtr,
Right_L_L_TailPtr);
{ connect current tree node to parent tree node according to passed parent branch ( or child type ) }
Case ParentBranch Of
ROOT : MST_RootPtr:=CurrentTreeNode;
LEFT : ParentTreeNode^.Left:=CurrentTreeNode;
RIGHT : ParentTreeNode^.Right:=CurrentTreeNode;
End; { Case ParentBranch }
{ build left son }
Build_MST_Node(Left_L_L_HeadPtr,
Left_L_L_TailPtr,
CurrentTreeNode,
LEFT);
{ build right son }
Build_MST_Node(Right_L_L_HeadPtr,
Right_L_L_TailPtr,
CurrentTreeNode,
RIGHT);
End; { If Not EmptyLinkedList }
End; { Build_MST_Node }
Begin { Build_MST_Module }
Build_MST_Node(L_L_HeadPtr,
L_L_TailPtr,
MST_RootPtr,
ROOT);
End; { Build_MST_Module }
Procedure Print_MST_Module;
{ *************************************************************************** }
{ * * }
{ * PRINT MEDIAN SPLIT TREE MODULE * }
{ * * }
{ * This module prints out the median split tree node data in a form * }
{ * representing the tree structure that it is stored in. It calls a * }
{ * recursive inorder traversal procedure 'PrintNodesInorder' that * }
{ * travels down the right most subtree first. * }
{ * * }
{ *************************************************************************** }
Const
Offset:Integer=15; { column offset used in printing of each tree level }
Type
ChildType=(LEFT,RIGHT,ROOT); { an enumerated data type used in printing out the proper branch for each child node }
Procedure Print_MST_Node( Node: TreeNodePtr;
Level: Integer;
Branch:ChildType);
{ This procedure prints out the MST node with the proper branch attached. }
Var
NodeElement:Integer; { a index counter to an array element }
Begin { Print_MST_Node }
If Node=Nil Then
Case Branch Of
ROOT : Begin
WriteLn(' ':Level*Offset,'Nil'); { write out split value }
WriteLn(' ':Level*Offset,'^ Split Key');
For NodeElement:=MAX_KEYS_PER_NODE DownTo ((MAX_KEYS_PER_NODE Div 2)+2) Do
WriteLn(' ':Level*Offset,'Nil'); { write out right elements }
WriteLn('-':Level*Offset,'Nil'); { write out center element }
For NodeElement:=(MAX_KEYS_PER_NODE Div 2) DownTo 1 Do
WriteLn(' ':Level*Offset,'Nil'); { write out left elements }
End;
RIGHT : Begin
WriteLn(' ':Level*Offset,'Nil'); { write out split value }
WriteLn(' ':Level*Offset,'^ Split Key');
For NodeElement:=MAX_KEYS_PER_NODE DownTo 2 Do
WriteLn(' ':Level*Offset,'Nil'); { write out elements }
WriteLn('/':Level*Offset,'Nil'); { write out left most element }
End;
LEFT : Begin
WriteLn(' ':Level*Offset,'Nil'); { write out split value }
WriteLn(' ':Level*Offset,'^ Split Key');
WriteLn('\':Level*Offset,'Nil'); { write out right most element }
For NodeElement:=MAX_KEYS_PER_NODE-1 Downto 1 Do
WriteLn(' ':Level*Offset,'Nil'); { write out elements }
End;
End { Case Branch }
Else { not a Nil node }
With Node^ Do
Case Branch Of
ROOT : Begin
If Length(SplitKey.Key)<>0 Then
WriteLn(' ':Level*Offset,SplitKey.Key,
' ',SplitKey.Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
WriteLn(' ':Level*Offset,'^ Split Key');
For NodeElement:=MAX_KEYS_PER_NODE DownTo ((MAX_KEYS_PER_NODE Div 2)+2) Do
If Length(NodeKeys[NodeElement].Key)<>0 Then
WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
' ',NodeKeys[NodeElement].Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
If Length(NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Key)<>0 Then
WriteLn('-':Level*Offset,NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Key,
' ',NodeKeys[(MAX_KEYS_PER_NODE Div 2)+1].Frequency)
Else
WriteLn('-':Level*Offset,'Nil');
For NodeElement:=(MAX_KEYS_PER_NODE Div 2) DownTo 1 Do
If Length(NodeKeys[NodeElement].Key)<>0 Then
WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
' ',NodeKeys[NodeElement].Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
End;
RIGHT : Begin
If Length(SplitKey.Key)<>0 Then
WriteLn(' ':Level*Offset,SplitKey.Key,
' ',SplitKey.Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
WriteLn(' ':Level*Offset,'^ Split Key');
For NodeElement:=MAX_KEYS_PER_NODE DownTo 2 Do
If Length(NodeKeys[NodeElement].Key)<>0 Then
WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
' ',NodeKeys[NodeElement].Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
If Length(NodeKeys[1].Key)<>0 Then
WriteLn('/':Level*Offset,NodeKeys[1].Key,
' ',NodeKeys[1].Frequency)
Else
WriteLn('/':Level*Offset,'Nil');
End;
LEFT : Begin
If Length(SplitKey.Key)<>0 Then
WriteLn(' ':Level*Offset,SplitKey.Key,
' ',SplitKey.Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
WriteLn(' ':Level*Offset,'^ Split Key');
If Length(NodeKeys[MAX_KEYS_PER_NODE].Key)<>0 Then
WriteLn('\':Level*Offset,NodeKeys[MAX_KEYS_PER_NODE].Key,
' ',NodeKeys[MAX_KEYS_PER_NODE].Frequency)
Else
WriteLn('\':Level*Offset,'Nil');
For NodeElement:=MAX_KEYS_PER_NODE-1 DownTo 1 Do
If Length(NodeKeys[NodeElement].Key)<>0 Then
WriteLn(' ':Level*Offset,NodeKeys[NodeElement].Key,
' ',NodeKeys[NodeElement].Frequency)
Else
WriteLn(' ':Level*Offset,'Nil');
End;
End; { Case Branch }
End; { Print_MST_Node }
Procedure PrintNodesInorder( Node: TreeNodePtr;
Level: Integer;
Branch:ChildType);
{ This recursive procedure is used to print the nodes of the median split
tree. It traverses the tree using an inorder traversal that goes to the
right most subtree first. }
Begin { PrintNodesInorder }
If Node=Nil Then { Nil child node }
Print_MST_Node(Node,level,Branch)
Else
Begin
PrintNodesInorder(Node^.Right,Level+1,RIGHT); { traverse right subtree }
Print_MST_Node(Node,Level,Branch);
PrintNodesInorder(Node^.Left,Level+1,LEFT); { traverse left subtree }
End; { Else }
End; { PrintNodesInorder }
Begin { Print_MST_Module }
WriteLn;
WriteLn;
WriteLn('MEDIAN SPLIT TREE FOLLOWS:');
WriteLn('--------------------------');
WriteLn;
WriteLn;
PrintNodesInorder(MST_RootPtr,0,ROOT);
End; { Print_MST_Module }
Procedure PrintQueryHeading;
{ This procedure prints out a heading for the search for matching look-up keys
for the file of queries. }
Begin { PrintQueryHeading }
WriteLn;
WriteLn;
WriteLn('QUERY SEARCH FOLLOWS:');
WriteLn('---------------------');
WriteLn;
WriteLn;
End; { PrintQueryHeading }
Procedure Search_MST_Module( Query: KeyString;
Var Found: Boolean;
Var NumberOfComparisons:Integer);
{ *************************************************************************** }
{ * * }
{ * SEARCH MEDIAN SPLIT TREE MODULE * }
{ * * }
{ * This module controls the looking up of the passed quiery with the * }
{ * entries in the median split tree. * }
{ * * }
{ *************************************************************************** }
Procedure InitModule;
{ This procedure initializes the variables used in this module. }
Begin { InitModule }
Found:=False;
NumberOfComparisons:=0;
End; { InitModule }
Procedure Search_MST_Node( ArrayOfKeys: KeyArray;
Query: KeyString;
Var Found: Boolean;
Var NumberOfComparisons:Integer);
{ This procedure performs a binary search on the passed array of look-up keys
to try to find a match with the passed query. If a match is found then the
Found boolean is returned as true. The NumberOfComparisons is also
returned. }
Var
LowElement:Integer; { an index to a low element in the passed array }
MidElement:Integer; { an index to a middle element in the passed array }
HighElement:Integer; { an index to a high element in the passed array }
Begin { Search_MST_Node }
{ initialize the index variables }
LowElement:=1;
HighElement:=MAX_KEYS_PER_NODE;
While (LowElement<=HighElement) And ( Not Found) Do
Begin
NumberOfComparisons:=NumberOfComparisons+1; { increment counter }
MidElement:=(LowElement+HighElement) Div 2; { determine mid point }
If Query<ArrayOfKeys[MidElement].Key Then
HighElement:=MidElement-1
Else
If Query>ArrayOfKeys[MidElement].Key Then
LowElement:=MidElement+1
Else
Found:=True;
End; { While LowElement }
End; { Search_MST_Node }
Procedure Search_MST( CurrentTreeNode: TreeNodePtr;
Query: KeyString;
Var Found: Boolean;
Var NumberOfComparisons:Integer);
Begin { Search_MST }
If CurrentTreeNode<>Nil Then
Begin
Search_MST_Node(CurrentTreeNode^.NodeKeys,
Query,
Found,
NumberOfComparisons);
If (Not Found) And (CurrentTreeNode^.SplitKey.Key<>'') Then
Begin
NumberOfComparisons:=NumberOfComparisons+1; { increment counter }
If Query=CurrentTreeNode^.SplitKey.Key Then
Found:=True
Else { continue search }
Begin
If Query<CurrentTreeNode^.SplitKey.Key Then
CurrentTreeNode:=CurrentTreeNode^.Left { point to left subtree }
Else
CurrentTreeNode:=CurrentTreeNode^.Right; { point to right subtree }
Search_MST(CurrentTreeNode,
Query,
Found,
NumberOfComparisons);
End; { Else }
End; { If Not Found }
End; { If CurrentTreeNode }
End; { Search_MST }
Begin { Search_MST_Module }
InitModule;
Search_MST(MST_RootPtr,
Query,
Found,
NumberOfComparisons);
End; { Search_MST_Module }
Procedure PrintSearchResults( Query: KeyString;
Found: Boolean;
NumberOfComparisons:Integer);
{ This procedure prints out the result from the look-up key search. }
Begin { PrintSearchResults }
If Not Found Then
WriteLn('The query ',Query,' was not found to exist in the median split tree.')
Else
WriteLn('The query ',Query,' was found in ',NumberOfComparisons,' comparisons.');
End; { PrintSearchResults }
Procedure ReadQueryFile;
{ This procedure reads queries from a query file, passes the query to a look-up
module to see idf the query exists in the MST and finally passes the result
of the search to a procedure to print the results of the search. }
Const
FILE_NAME='Query1.Dat'; { name of the query data file }
Type
FileEntryString=String[MAX_KEY_SIZE]; { a string type used to store file entries }
Var
QueryFile:Text; { text file }
FileEntry:FileEntryString; { variable used in reading the queries in teh query file }
Found:Boolean; { a boolean flag used to determine if a query is in the MST }
NumberOfComparisons:Integer; { a counter used to determine the number of comparisons required
to find a particular query in the MST }
Begin { ReadQueryFile }
Assign(QueryFile,FILE_NAME); { assign to a disk file }
Reset(QueryFile); { open the file for reading }
Repeat
ReadLn(QueryFile,FileEntry); { read in the file entry }
Search_MST_Module(FileEntry,
Found,
NumberOfComparisons);
PrintSearchResults(FileEntry,
Found,
NumberOfComparisons);
Until Eof(QueryFile); { read until end of file found }
Close(QueryFile); { close the disk file }
End; { ReadQueryFile }
Begin { Main Program }
InitProgram;
HardCopy(False);
ReadInputFileModule;
PrintLinkedList(L_L_HeadPtr,L_L_TailPtr);
Build_MST_Module;
Print_MST_Module;
PrintQueryHeading;
ReadQueryFile;
End. { Main Program }